//
// Created by Tiany on 2021/6/18.
//

#include <stdlib.h>
#include <stdio.h>
#include "LinkList.h"

//创建空链表
LinkList createNullList_link(void) {
    LinkList linkList = (LinkList) malloc(sizeof(struct Node));
    if (linkList != NULL) {
        linkList->link = NULL;
    } else printf("空间申请失败！");
    return linkList;
}

//判断单链表是否为空
int isNullList_link(LinkList linkList) {
    return (linkList->link == NULL);/*单链表为空则返回1*/
}

//在单链表中求某元素的存储位置
PNode locate_link(LinkList linkList, struct DataType x) {
    PNode pNode;
    if (linkList == NULL) {
        printf("单链表为空，请检查数据");
        return NULL;
    }
    pNode = linkList->link;
    while (pNode != NULL && pNode->info.n != x.n) {
        pNode = pNode->link;
    }
    return pNode;
}

//在单链表中求p结点的前驱结点
PNode locatePre_link(LinkList linkList, PNode p) {
    PNode pNode;
    if (linkList == NULL)
        return NULL;
    pNode = linkList;
    while (pNode != NULL && pNode->link != p)
        pNode = pNode->link;
    return pNode;
}

//单链表的p结点后插入
int insertPost_link(LinkList linkList, PNode p, struct DataType x) {
    if (linkList == NULL) {
        printf("单链表为空，请检查数据输入！");
        return 0;
    } else {
        PNode q = (PNode) malloc(sizeof(struct Node));
        if (q != NULL) {
            q->info = x;
            q->link = p->link;
            p->link = q;
            return 1;
        }
    }
    return 0;
}

//单链表的p结点前插入
int insertPre_link(LinkList linkList, PNode p, struct DataType x) {
    PNode pNode = locatePre_link(linkList, p);/*先找到前驱结点*/
    return insertPost_link(linkList, pNode, x);/*再在前驱结点后插入新结点*/
}

//在单链表中删除元素x
int deleteV_link(LinkList linkList, struct DataType x) {
    PNode pNode, qNode;
    pNode = linkList;
    if (pNode == NULL)
        return 0;
    while (pNode->link != NULL && pNode->link->info.n != x.n)
        pNode = pNode->link;
    if (pNode->link == NULL) {
        printf("单链表为空，请检查数据！");
        return 0;
    } else {
        qNode = pNode->link;
        pNode->link = qNode->link;
        free(qNode);
        return 1;
    }
}

//在单链表中删除结点p
int deleteP_link(LinkList linkList, PNode p) {
    PNode pNode;
    pNode = locatePre_link(linkList, p);
    return deleteV_link(linkList, pNode->info);
}

//去除单链表中重复的元素
int delete_duplicate(LinkList linkList) {
    for (int i = 0; i < length_link(linkList); i++) {
        PNode pNode;
        pNode = linkList->link;
        while (countV_link(linkList, pNode->info) > 1) {/*数组中存在该元素的个数大于1，则删掉一个*/
            deleteV_link(pNode, pNode->info);
            //pNode=pNode->link;
        }
        linkList = linkList->link;
    }
}

//查找单链表中元素x的个数
int countV_link(LinkList linkList, struct DataType x) {
    PNode pNode;
    int count = 0;
    pNode = linkList->link;
    while (pNode != NULL) {
        if (pNode->info.n == x.n) {
            count++;
        }
        pNode = pNode->link;
    }
    return count;
}

//求单链表的长度
int length_link(LinkList linkList) {
    int length = 0;
    while (!isNullList_link(linkList)) {
        length++;
        linkList = linkList->link;
    }
    return length;
}

//将数据写入单链表
LinkList writeList_link(LinkList linkList, struct DataType x[], int length) {
    if (linkList != NULL) {
        PNode pNode = linkList;/*记录头结点*/
        for (int i = 0; i < length; i++) {
            LinkList l = createNullList_link();
            if (l != NULL) {
                linkList->link = l;
                l->info.n = x[i].n;
                linkList = l;
            }
        }
        return pNode;
    } else return NULL;
}

//读取并打印单链表
void readList_link(LinkList linkList) {
    if (linkList != NULL) {
        printf("\n链表数据为：");
        while (linkList->link) {
            printf("%d  ", linkList->link->info.n);
            linkList = linkList->link;
        }
    }
}